package junior.图;

import java.util.Scanner;

public class queen8_02 {
    static int[] queenPos = new int[13];
    static int count=0,n;   //存储每种可行的结果  n：棋盘大小
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (1 == 1){
            n = input.nextInt();
            long startTime = System.currentTimeMillis();
            queen(0);
            long endTime = System.currentTimeMillis();
            System.out.println(n+" 皇后总方案数："+count);
            System.out.println(endTime -startTime);
            count = 0;
        }
    }
    // 递归：函数栈（栈里面保存每个函数的现场）
    //      （1）结束条件，”函数现场“退栈，回到上面一个状态，直到递归结束（过程）
    //      （2）函数递归，回到上面一个状态，执行上一个函数的状态（循化，打或去标记，保存结果）
    // 关键：（1）递归的函数个数，一般与递归参数和函数内部的循环，关系最大
    //      （2）递归的过程中，保存结果，打标记等等，要用到全局变量，用于保存结果，控制递归走向
    //      （3）难点一般是：如何打标记，如何进行递归判断
    static void queen(int k) {
        int i,j;
        if (k == n) {
            for (i = 0; i < n; i++)
                System.out.print(queenPos[i] + 1 +" ");
            System.out.println();
            System.out.println("************************");
            show(queenPos,n);
            System.out.println("************************");
            count++;
            return;
        }
        for(i=0;i<n;i++){       //i：递归当前行的某一列               j：以递归的某一行       queenPos[j]：j行的某一列
            for(j=0;j<k;j++){   //k行的i列（k，i），与前面的位置进行比较        行距离         列距离  ( 相等即为在对角线上，45度直角三角形 )
                if(i == queenPos[j] || Math.abs(queenPos[j]-i) == Math.abs(k-j))   ///判断line行的 i 位是否被占领  1：否
                    break;
            }                       // 无结果、返回上一个函数现场
            if(j==k){               // 前j行的皇后都为占领该位置，就j++即为当前递归的行
                queenPos[k] = i ;
                queen(k+1);      // 遇return、返回上一个函数现场
            }
        }
    }
    static void show(int[] queenPos,int n){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(queenPos[i] == j)
                    System.out.print(0+" ");
                else
                    System.out.print("*"+" ");
            }
            System.out.println();
        }
    }
}
